Search Results

Documents authored by Hengeveld, Simon B.


Document
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem

Authors: Simon B. Hengeveld and Tillmann Miltzow

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Given a closed simple polygon P, we say two points p,q see each other if the segment seg(p,q) is fully contained in P. The art gallery problem seeks a minimum size set G ⊂ P of guards that sees P completely. The only currently correct algorithm to solve the art gallery problem exactly uses algebraic methods. As the art gallery problem is ∃ ℝ-complete, it seems unlikely to avoid algebraic methods, for any exact algorithm, without additional assumptions. In this paper, we introduce the notion of vision-stability. In order to describe vision-stability consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is by an angle of δ "blocked" by reflex vertices. A polygon P has vision-stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot vision-stable algorithm that computes an optimal guard set for vision-stable polygons using polynomial time and solving one integer program. It guarantees to find the optimal solution for every vision-stable polygon. We implemented an iterative vision-stable algorithm and show its practical performance is slower, but comparable with other state-of-the-art algorithms. The practical implementation can be found at: https://github.com/simonheng/AGPIterative. Our iterative algorithm is inspired and follows closely the one-shot algorithm. It delays several steps and only computes them when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-visibility width (cw(P)) of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admit an FPT algorithm when parameterized by the chord-visibility width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices.

Cite as

Simon B. Hengeveld and Tillmann Miltzow. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{hengeveld_et_al:LIPIcs.SoCG.2021.44,
  author =	{Hengeveld, Simon B. and Miltzow, Tillmann},
  title =	{{A Practical Algorithm with Performance Guarantees for the Art Gallery Problem}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{44:1--44:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.44},
  URN =		{urn:nbn:de:0030-drops-138433},
  doi =		{10.4230/LIPIcs.SoCG.2021.44},
  annote =	{Keywords: Art Gallery, Parametrized complexity, Integer Programming, Visibility}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail